package com.datastructure.test.maxsumofbinarytree;

public class MaxSumOfBinaryTree {

    public static void main(String[] args) {
        MaxSumOfBinaryTree maxSumOfBinaryTree = new MaxSumOfBinaryTree();

    }

    int ans = Integer.MIN_VALUE;
    public int maxPathSum (TreeNode root) {
        // write code here
        if(root==null){
            return 0;
        }
        dfs(root);
        return ans;
    }

    public int dfs(TreeNode root){
        if(root==null){
            return 0;
        }
        //计算左孩子贡献
        int leftMax = Math.max(dfs(root.left),0);
        //计算右孩子贡献
        int rightMax = Math.max(dfs(root.right),0);
        //更新答案
        ans = Math.max(ans,root.val+leftMax+rightMax);
        //返回当前节点的总贡献
        return root.val+Math.max(leftMax,rightMax);
    }
}

class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;
 }
